#include <iostream>
#include <stack>

using namespace std;

//第一题，二叉查找树的反转
struct Node
{
    int element;
    Node *lc;
    Node *rc;
    Node(){lc=rc=NULL;}
    Node(int theElement,Node *le=NULL,Node *ri=NULL)
    {
        element=theElement;
        lc=le;
        rc=ri;
    }
};

class Find_tree
{
public:
    Node *root;

public:
    Find_tree() {
        root=NULL;
    }

    // FIXME:
    //  1. 命名不规范，`Create`函数名，你其他的函数用的是小写，这里最好也是小写开头
    //  2. 参数`Node *&p`搞得太复杂了，可以把生成的节点返回，这样好理解，也符合通常的做法
    void Creat(Node *&p,int num){
        //这里传参的时候要将root的地址一块传进来，否则root一直是NULL
        if(p==NULL){
            Node *newnode= new Node;
            newnode-> element=num;
            newnode->lc = NULL;
            newnode->rc = NULL;
            p = newnode;
        }
        else{
            if(p->element > num){
                Creat(p->lc,num);
            }
            else{
                Creat(p->rc,num);
            }
        }
    }

    void reverse(Node *root)
    {
        //所谓树的镜像只需交换每一个结点的左右孩子即可
        if (root->lc && root->rc)
        {
            Node *temp=root->lc;
            root->lc=root->rc;
            root->rc=temp;
            if (root->lc)
            {
                reverse(root->lc);
            }
            if (root->rc)
            {
                reverse(root->rc);
            }
        }
    }

    void pre(Node *root)
    {
        if(root)
        {
            cout<<root->element<<",";
            pre(root->lc);
            pre(root->rc);
        }
    }

};

int main()
{

    Find_tree t1;
    int a[7]={8,6,5,7,10,9,11};
    for (int i=0;i<7;i++)
    {
        t1.Creat(t1.root, a[i]);
        //cout<<t1.root<<endl;
    }
    t1.pre(t1.root);
    cout<<endl;
    t1.reverse(t1.root);
    t1.pre(t1.root);
    return 0;
}

// FIXME:
//  1. 注意格式、命名等。不过现在功力不够深的时候，可以先把功能实现了，然后等确认程序没有问题的情况下，可以专门检查、反思一下程序哪里不规范
//  2. 坚持锻炼程序，编程、算法思维不容易突击提高，需要一点一点练习。等你练到一定量，突然会发现自己的功力大增，写程序会非常顺手，会有很大的成就感。希望你早日到达这样的境界!
